package com.jia.explore.tree.segmenttree;

import java.util.Arrays;

/**
 * @program: Leetcode
 * @description: 线段树
 *              线段树，计算数组a[0..n]范围的和sum(i,j) 和 更新每个数组某个下表的值update(i)
 *              1.平常进行数组a[0..n]进行扫描计算sum(i,j)时间复杂度为O(n), update(i)时间复杂度为O(1)
 *              2.如果使用前缀和sum[0..n]记录i前项和，那么sum(i,j) = sum[j] - sum[i-1], 那么空间复杂度为O(1),
 *                  update(i)的时候需要更新sum[i..n]的值，所以时间复杂度为O(n)
 *              3.线段树就是平衡解决sum(i,j)和update(i)的操作的，时间复杂度都为O(logn);
 *
 *              例如：数组a为{1,3,5,7,9,11} 下表[0,1,2,3,4,5]
 *              那么线段树可以表示为[下表]和
 *                          [0..5]36
 *                [0..2]9                    [3,5]27
 *           [0..1]4      [1]5          [3,4]16        [5]11
 *        [0]1   [1]3   [空] [空]      [3]7  [4]9     [空]   [空]
 *        那么可以存储为tree{36,9,27,4,5,16,11,1,3,null,null,7,9,null,null}
 *        根据二叉树的性质： 当前节点node的下表为index，那么左节点left_index = 2 * index + 1，右节点right_index = 2 * index + 2;
 * @author: STU756
 * @create: 2020-08-17 13:25
 */
public class SegmentTree {
    public static void main(String[] args) {
        int MAX_LEN = 100;
        int[] a = {1,3,5,7,9,11};
        int size = a.length;
        int[] tree = new int[1 << ((size + 1)/ 2 + 1) ];
//        int[] tree = new int[MAX_LEN ];
        build_tree(a, tree, 0, 0, size - 1);
        System.out.println(Arrays.toString(tree));
        System.out.println(query_tree(a, tree, 0, 0, size - 1, 0,5));
        update_tree(a, tree, 0, 0, size - 1, 4, 6);
        System.out.println(Arrays.toString(tree));

    }

    /**
     * 计算[L..R]的和
     * @param a
     * @param tree
     * @param index
     * @param st
     * @param ed
     * @param L
     * @param R
     * @return [L..R]的和
     */
    static  int query_tree(int[] a, int[] tree, int index, int st, int ed, int L, int R) {
        //递归终止条件
        if(R < st || ed < L) {
            // [st, ed, L, R] 或[L, R, st, ed]
            return 0;
        }else if(L<= st && ed <= R){
            //[L, st, ed, R]
            return tree[index];
        }else if(st == ed) {
            return tree[index];
        }else {
            int mid = (st + ed) >> 1;
            int left_index = index * 2 + 1;
            int right_index = index * 2 + 2;
            int sum_left = query_tree(a, tree, left_index, st, mid, L, R);
            int sum_right = query_tree(a, tree, right_index, mid + 1, ed, L, R);
            return sum_left + sum_right;
        }
    }

    /**
     * 更改下标为idx的值为val
     * @param a
     * @param tree
     * @param index
     * @param st
     * @param ed
     * @param idx  更改的下表
     * @param val  更改的值
     */
    private static void update_tree(int[] a, int[] tree, int index, int st, int ed, int idx, int val) {
        if(st == ed) {
            a[idx] = val;
            tree[index] = val;
        }else {
            int mid = st + ((ed - st) >> 1);
            int left_index = 2 * index + 1;
            int right_index = 2 * index + 2;
            if (idx >= st && idx <= mid) {
                update_tree(a, tree, left_index, st, mid, idx, val);
            } else {
                update_tree(a, tree, right_index, mid + 1, ed, idx, val);
            }
            tree[index] = tree[left_index] + tree[right_index];
        }
    }

    /**
     * 建立线段树
     * @param a  数组
     * @param tree 存储线段树的数组
     * @param index  当前下标节点
     * @param st     线段树线段的开始下标
     * @param ed     线段树线段的结束下标
     */
    private static void build_tree(int[] a, int[] tree, int index, int st, int ed) {
        if(st == ed) {
            tree[index] = a[st];
        }else {
            int mid =(st + ed) >> 1;
            int left_index = index * 2 + 1;
            int right_index = index * 2 + 2;
            build_tree(a, tree, left_index, st, mid);
            build_tree(a, tree, right_index, mid + 1, ed);
            tree[index] = tree[left_index] + tree[right_index];
        }
    }
}
